package com.zjsru.binaryeasy;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/8/6
 * 在排序数组中查找元素的第一个和最后一个位置
 *  给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 *
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 *
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 */
public class SearchRange {
    /**
     * 暴力算法
     * ans的长度被固定住了
     */
    public int[] searchRange1(int[] nums, int target) {
        int[] ans = new int[2];
        int j = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == target){
                ans[j] = i;
                j++;
            }
        }
       if(ans[0] > ans[1]){
           ans[1] = ans[0];
       }
        if(Arrays.stream(nums).filter(num -> num == target).count() == 0){
            return new int[]{-1,-1};
        }
        return ans;
    }
    
    /**
     * 二分算法
     * 二分查找中，寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标，寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标，然后将下标减一。
     *
     * 如果 lower 为 true，则查找第一个大于等于 target 的下标，否则查找第一个大于 target 的下标。
     *
     */
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }
    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        SearchRange searchRange = new SearchRange();
        int[] nums = new int[]{1,4};
        int target = 4;
        System.out.println(searchRange.searchRange(nums, target));
    }
}
